# https://leetcode.cn/problems/open-the-lock/description/

from collections import deque


class Solution:
    @staticmethod
    def openLock(deadends: list[str], target: str) -> int:
        if "0000" == target:
            return 0
        deadends = set(deadends)
        if target in deadends or "0000" in deadends:
            return -1

        notAnswer = set(deadends)
        pt = deque(["0000"])
        notAnswer.add("0000")
        res = 0

        while pt:
            ptSize = len(pt)
            for _ in range(ptSize):
                password = pt.popleft()
                if password == target:
                    return res
                for i in range(4):
                    for d in (-1, 1):
                        temp = password[:i] + str((int(password[i]) + d + 10) % 10) + password[i + 1:]
                        if temp not in notAnswer:
                            pt.append(temp)
                            notAnswer.add(temp)
            res += 1
        return -1
